home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_10_02 / 1002060a < prev    next >
Encoding:
Text File  |  1991-12-11  |  10.3 KB  |  464 lines
  1.  
  2.  
  3.  
  4.       
  5.        /***********************************************
  6.        *
  7.        *       file d:\lsu\cujhuff2.c
  8.        *
  9.        **********************************************/
  10.  
  11.  
  12.  
  13. #include "d:\lsu\cujhuff.h"
  14.  
  15.  
  16.  
  17.  
  18.  
  19. /*         
  20.        create_huffman_code(item_array)
  21.  
  22.        This routine is the top of the routines that create 
  23.        the codes.  Create the codes xxxxx010 for the characters
  24.        read in.  You use the item_array which contains the
  25.        counts of occurances and so on.
  26. */
  27.  
  28.  
  29. create_huffman_code(item_array)
  30.    struct item_struct item_array[];
  31. {
  32.    int    counter, 
  33.           i,
  34.           not_ended;
  35.    struct item_struct temp;
  36.  
  37.    sort_item_array(item_array);
  38.    disable_zero_counts(item_array);
  39.  
  40.           /***********************************
  41.           *
  42.           *  The following short loop is the
  43.           *  heart of the algorithm.  The 
  44.           *  rest is the implementation detail
  45.           *  which is not trivial.
  46.           *
  47.           *************************************/
  48.  
  49.    counter   = 0;
  50.    not_ended = 1;
  51.    while(not_ended){
  52.       if( (counter % 50) == 0) printf("\n> Creating code ");
  53.       printf(".");
  54.       combine_and_code_2_smallest_items(item_array, ¬_ended);
  55.       sort_item_array(item_array);
  56.       counter++;
  57.    }  /* ends while not_ended  */
  58.  
  59.    reverse_order_of_coded(item_array);
  60.  
  61.  
  62. }  /* ends create_huffman_code        */
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69. /*  
  70.      sort_item_array(item_array)
  71.  
  72.      This is a very simple bubble sort algorithm.
  73.      It does use the Microsoft C ability to
  74.      set one struct equal to another.  Some
  75.      compilers do not support this.
  76.  */
  77.  
  78.  
  79. sort_item_array(item_array)
  80.    struct item_struct item_array[];
  81. {
  82.    int    i,
  83.           not_finished,
  84.           swapped;
  85.    struct item_struct temp;
  86.  
  87.    not_finished = 1;
  88.  
  89.    while(not_finished){
  90.       swapped = 0;
  91.       for(i=0; i<LENGTH-1; i++){
  92.          if(item_array[i].count < item_array[i+1].count){
  93.             swapped         = 1;
  94.             temp            = item_array[i];
  95.             item_array[i]   = item_array[i+1];
  96.             item_array[i+1] = temp;
  97.          }  /* ends if you need to swap  */
  98.       }     /* ends loop over i          */
  99.       if(swapped == 0)
  100.          not_finished = 0;
  101.    }  /* ends while not_finished  */
  102.  
  103.  
  104.        /*   Perform an extra pass through the sort to 
  105.             ensure all 'D'isbaled items are below all
  106.             'E'nabled items in the item_array  */
  107.  
  108.    not_finished = 1;
  109.  
  110.    while(not_finished){
  111.       swapped = 0;
  112.       for(i=0; i<LENGTH-1; i++){
  113.          if(  (item_array[i].indicator   == 'D') &&
  114.               (item_array[i+1].indicator == 'E')){
  115.             swapped         = 1;
  116.             temp            = item_array[i];
  117.             item_array[i]   = item_array[i+1];
  118.             item_array[i+1] = temp;
  119.          }  /* ends if you need to swap  */
  120.       }     /* ends loop over i          */
  121.  
  122.       if(swapped == 0)
  123.          not_finished = 0;
  124.    }  /* ends while not_finished  */
  125.  
  126.  
  127. }     /* ends sort_item_array          */
  128.  
  129.  
  130.  
  131.  
  132.  
  133. /*    
  134.           disable_zero_counts(item_array)
  135.  
  136.           You do not want to work on the characters
  137.           that were not in the input file so you
  138.           disable them.
  139. */
  140.  
  141. disable_zero_counts(item_array)
  142.    struct item_struct item_array[];
  143. {
  144.    int i;
  145.  
  146.    for(i=0; i<LENGTH; i++){
  147.       if(item_array[i].count == 0)
  148.          item_array[i].indicator = 'D';
  149.    }  /* ends loop over i  */
  150. }  /* ends disable_zero_counts        */
  151.  
  152.  
  153.  
  154.  
  155. /*  
  156.      combine_and_code_2_smallest_items(item_array, not_ended)
  157.  
  158.      This function calls other functions to find the two
  159.      smallest items and then combine or link them.
  160.  
  161. */
  162.  
  163. combine_and_code_2_smallest_items(item_array, not_ended)
  164.    struct item_struct item_array[];
  165.    int          *not_ended;
  166. {
  167.    char r[80];
  168.    int next_smallest, smallest;
  169.  
  170.  
  171.    find_smallest_item(item_array, &smallest);
  172.    if(smallest <= 0){
  173.       *not_ended = 0;
  174.    }
  175.  
  176.    else{
  177.       next_smallest = smallest;
  178.       find_next_smallest_item(item_array, &next_smallest);
  179.       code_2_smallest_items(item_array, smallest, next_smallest);
  180.       combine_2_smallest_items(item_array, smallest,
  181. next_smallest);
  182.  
  183.    }
  184.  
  185. }  /* ends combine_and_code_2_smallest_items  */
  186.  
  187.  
  188.  
  189.  
  190.  
  191. /*
  192.               find_smallest_item(item_array, smallest)
  193.  
  194.  
  195.               You are working with a sorted item_array
  196.               so you start looking at the bottom of the
  197.               array.  You look until you find the first
  198.               'E'nabled indicator then you stop.
  199. */
  200.  
  201. find_smallest_item(item_array, smallest)
  202.    struct item_struct item_array[];
  203.    int          *smallest;
  204. {
  205.    int i,
  206.        searching;
  207.  
  208.    *smallest = 0;
  209.    searching = 1;
  210.    i             = 255;
  211.  
  212.    while(searching){
  213.       if(item_array[i].indicator == 'E'){
  214.          *smallest = i;
  215.          searching = 0;
  216.       }  /* ends if indicator == 'E'  */
  217.  
  218.       else{
  219.          i = i-1;
  220.          if(i<0){
  221.             *smallest = -1;
  222.             searching = 0;
  223.          }
  224.       }  /* ends else indicator != 'E'        */
  225.    }         /* ends while searching        */
  226. }         /* ends find_smallest_item        */
  227.  
  228.  
  229.  
  230.  
  231.  
  232. /*    
  233.               find_next_smallest_item(item_array, next_smallest)
  234.  
  235.               You are working with a sorted item_array
  236.               so you start looking at the smallest item of the
  237.               array.  You look until you find the first
  238.               'E'nabled indicator then you stop.
  239. */
  240.  
  241. find_next_smallest_item(item_array, next_smallest)
  242.    struct item_struct item_array[];
  243.  
  244.    int          *next_smallest;
  245. {
  246.    int i,
  247.        searching;
  248.  
  249.    searching = 1;
  250.    i         = *next_smallest-1;
  251.  
  252.    while(searching){
  253.       if(item_array[i].indicator == 'E'){
  254.          *next_smallest = i;
  255.          searching = 0;
  256.       }  /* ends if indicator == 'E'  */
  257.  
  258.       else{
  259.          i = i-1;
  260.          if(i<0){
  261.             *next_smallest = -1;
  262.             searching = 0;
  263.          }
  264.       }  /* ends else indicator != 'E'        */
  265.    }         /* ends while searching        */
  266. }         /* ends find_next_smallest_item        */
  267.  
  268.  
  269.  
  270.  
  271.  
  272.  
  273.  
  274. /*    
  275.             combine_2_smallest_items(...
  276.  
  277.             . add the two counts together
  278.             . disable the smallest one
  279.             . link the smallest one to the next smallest one
  280. */
  281.          
  282. combine_2_smallest_items(item_array, smallest, next_smallest)
  283.    struct item_struct item_array[];
  284.    int    next_smallest, smallest;
  285. {
  286.    int i, not_finished;
  287.  
  288.    item_array[next_smallest].count    = item_array[smallest].count
  289. +
  290.                                        
  291. item_array[next_smallest].count;
  292.  
  293.    item_array[smallest].count = item_array[next_smallest].count;
  294.  
  295.    item_array[smallest].indicator  = 'D';
  296.  
  297.     i = 0;
  298.     not_finished = 1;
  299.     while(not_finished){
  300.        if(item_array[next_smallest].includes[i] == 256){
  301.           item_array[next_smallest].includes[i] = smallest;
  302.           not_finished = 0;
  303.        }
  304.  
  305.        else{
  306.           i++;
  307.           if(i > LLENGTH){
  308.              printf("\n\n> Ran out of links\n\n");
  309.              exit(1);
  310.           }
  311.        }
  312.     } /* ends while not_finished */
  313.  
  314. }  /* ends combine_2_smallest_items  */
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321. /*    
  322.           code_2_smallest_items(...
  323.  
  324.           The smallest item is coded with a ONE
  325.           The next smallest item is coded with a ZERO
  326. */
  327.  
  328.  
  329. code_2_smallest_items(item_array, smallest, next_smallest)
  330.    struct item_struct item_array[];
  331.    int    next_smallest, smallest;
  332. {
  333.   
  334.    code_smallest_item(item_array, smallest);
  335.    code_next_smallest_item(item_array, next_smallest);
  336.  
  337. }  /* code_2_smallest_items  */
  338.  
  339.  
  340.  
  341. /*   
  342.            code_smallest_item(item_array, smallest)
  343.  
  344.            You must code the item as well as
  345.            all the other items included with it
  346.            on down to the end.
  347.         
  348.            Set the code to ONE.
  349. */
  350.  
  351.  
  352. code_smallest_item(item_array, smallest)
  353.    struct item_struct item_array[];
  354.    short smallest;
  355. {
  356.  
  357.  
  358.    int i,
  359.        j,
  360.        k,
  361.        setting;
  362.    
  363.       j       = smallest;
  364.       setting = 1;
  365.  
  366.       i       = 0;
  367.  
  368.          /* set code ONE  */
  369.       while(setting){
  370.          if(item_array[j].coded[i] == OTHER){
  371.             item_array[j].coded[i] = ONE;
  372.             setting = 0;
  373.          }  /* ends if == OTHER  */
  374.  
  375.          else
  376.             i++;
  377.       }  /* ends while setting             */
  378.          /* Recursive calls */
  379.       for(k=0; k<LLENGTH; k++)
  380.          if(item_array[j].includes[k] != 256)
  381.             code_smallest_item(item_array,
  382. item_array[j].includes[k]);
  383.  
  384. }         /* ends code_smallest_item  */
  385.  
  386.  
  387.  
  388. /*    
  389.            code_next_smallest_item(item_array, smallest)
  390.  
  391.            You must code the item as well as
  392.            all the other items included with it
  393.            on down to the end.
  394.         
  395.            Set the code to ZERO
  396. */
  397.  
  398. code_next_smallest_item(item_array, smallest)
  399.    struct item_struct item_array[];
  400.    short smallest;
  401. {
  402.  
  403.  
  404.    int i,
  405.        j,
  406.        k,
  407.        setting;
  408.    
  409.       j       = smallest;
  410.       setting = 1;
  411.       i       = 0;
  412.  
  413.          /* set code ZERO  */
  414.       while(setting){
  415.          if(item_array[j].coded[i] == OTHER){
  416.             item_array[j].coded[i] = ZERO;
  417.             setting = 0;
  418.          }  /* ends if == OTHER  */
  419.  
  420.          else
  421.             i++;
  422.       }  /* ends while setting             */
  423.  
  424.          /* Recursive calls */
  425.       for(k=0; k<LLENGTH; k++)
  426.  
  427.          if(item_array[j].includes[k] != 256)
  428.             code_next_smallest_item(item_array, 
  429.                      item_array[j].includes[k]);
  430.  
  431. }  /* ends code_next_smallest_item */
  432.  
  433.  
  434.  
  435.  
  436.  
  437.  
  438.  
  439. /*  
  440.           reverse_order_of_coded(item_array)
  441.  
  442.           Now trace backwards 
  443. */
  444.  
  445.  
  446. reverse_order_of_coded(item_array)
  447.    struct item_struct item_array[];
  448. {
  449.    char temp;
  450.    int  i, j;
  451.  
  452.    for(i=0; i<LENGTH; i++){
  453.       if(item_array[i].coded[0] != OTHER){
  454.          for(j=0; j<(CODE_LENGTH/2); j++){
  455.             temp                     = item_array[i].coded[j];
  456.             item_array[i].coded[j]   =
  457. item_array[i].coded[CODE_LENGTH-1-j];
  458.             item_array[i].coded[CODE_LENGTH-1-j] = temp;
  459.          }  /* ends loop over j           */
  460.       }     /* ends if coded[0] != OTHER  */
  461.    }        /* ends loop over i           */
  462. }           /* reverse_order_of_coded     */
  463. /* End of File */
  464.